home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 58 / pcpp58a.iso / extras / quake 3 source / Q3A_ToolSource.exe / Main / light_trace.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-02  |  21.8 KB  |  924 lines
  1. #include "light.h"
  2.  
  3.  
  4.  
  5. #define    CURVE_FACET_ERROR    8
  6.  
  7. int                c_totalTrace;
  8. int                c_cullTrace, c_testTrace;
  9. int                c_testFacets;
  10.  
  11. surfaceTest_t    *surfaceTest[MAX_MAP_DRAW_SURFS];
  12.  
  13. /*
  14. =====================
  15. CM_GenerateBoundaryForPoints
  16. =====================
  17. */
  18. void CM_GenerateBoundaryForPoints( float boundary[4], float plane[4], vec3_t a, vec3_t b ) {
  19.     vec3_t    d1;
  20.  
  21.     // amke a perpendicular vector to the edge and the surface
  22.     VectorSubtract( b, a, d1 );
  23.     CrossProduct( plane, d1, boundary );
  24.     VectorNormalize( boundary, boundary );
  25.     boundary[3] = DotProduct( a, boundary );
  26. }
  27.  
  28. /*
  29. =====================
  30. TextureMatrixFromPoints
  31. =====================
  32. */
  33. void TextureMatrixFromPoints( cFacet_t *f, drawVert_t *a, drawVert_t *b, drawVert_t *c ) {
  34.     int            i, j;
  35.     float        t;
  36.     float        m[3][4];
  37.     float        s;
  38.  
  39.     // This is an incredibly stupid way of solving a three variable equation
  40.     for ( i = 0 ; i < 2 ; i++ ) {
  41.  
  42.         m[0][0] = a->xyz[0];
  43.         m[0][1] = a->xyz[1];
  44.         m[0][2] = a->xyz[2];
  45.         m[0][3] = a->st[i];
  46.  
  47.         m[1][0] = b->xyz[0];
  48.         m[1][1] = b->xyz[1];
  49.         m[1][2] = b->xyz[2];
  50.         m[1][3] = b->st[i];
  51.  
  52.         m[2][0] = c->xyz[0];
  53.         m[2][1] = c->xyz[1];
  54.         m[2][2] = c->xyz[2];
  55.         m[2][3] = c->st[i];
  56.  
  57.         if ( fabs(m[1][0]) > fabs(m[0][0]) && fabs(m[1][0]) > fabs(m[2][0]) ) {
  58.             for ( j = 0 ; j < 4 ; j ++ ) {
  59.                 t = m[0][j];
  60.                 m[0][j] = m[1][j];
  61.                 m[1][j] = t;
  62.             }
  63.         } else if ( fabs(m[2][0]) > fabs(m[0][0]) && fabs(m[2][0]) > fabs(m[1][0]) ) {
  64.             for ( j = 0 ; j < 4 ; j ++ ) {
  65.                 t = m[0][j];
  66.                 m[0][j] = m[2][j];
  67.                 m[2][j] = t;
  68.             }
  69.         }
  70.  
  71.         s = 1.0 / m[0][0];
  72.         m[0][0] *= s;
  73.         m[0][1] *= s;
  74.         m[0][2] *= s;
  75.         m[0][3] *= s;
  76.  
  77.         s = m[1][0];
  78.         m[1][0] -= m[0][0] * s;
  79.         m[1][1] -= m[0][1] * s;
  80.         m[1][2] -= m[0][2] * s;
  81.         m[1][3] -= m[0][3] * s;
  82.  
  83.         s = m[2][0];
  84.         m[2][0] -= m[0][0] * s;
  85.         m[2][1] -= m[0][1] * s;
  86.         m[2][2] -= m[0][2] * s;
  87.         m[2][3] -= m[0][3] * s;
  88.  
  89.         if ( fabs(m[2][1]) > fabs(m[1][1]) ) {
  90.             for ( j = 0 ; j < 4 ; j ++ ) {
  91.                 t = m[1][j];
  92.                 m[1][j] = m[2][j];
  93.                 m[2][j] = t;
  94.             }
  95.         }
  96.  
  97.         s = 1.0 / m[1][1];
  98.         m[1][0] *= s;
  99.         m[1][1] *= s;
  100.         m[1][2] *= s;
  101.         m[1][3] *= s;
  102.  
  103.         s = m[2][1];
  104.         m[2][0] -= m[1][0] * s;
  105.         m[2][1] -= m[1][1] * s;
  106.         m[2][2] -= m[1][2] * s;
  107.         m[2][3] -= m[1][3] * s;
  108.  
  109.         s = 1.0 / m[2][2];
  110.         m[2][0] *= s;
  111.         m[2][1] *= s;
  112.         m[2][2] *= s;
  113.         m[2][3] *= s;
  114.  
  115.         f->textureMatrix[i][2] = m[2][3];
  116.         f->textureMatrix[i][1] = m[1][3] - f->textureMatrix[i][2] * m[1][2];
  117.         f->textureMatrix[i][0] = m[0][3] - f->textureMatrix[i][2] * m[0][2] - f->textureMatrix[i][1] * m[0][1];
  118.  
  119.         f->textureMatrix[i][3] = 0;
  120. /*
  121.         s = fabs( DotProduct( a->xyz, f->textureMatrix[i] ) - a->st[i] );
  122.         if ( s > 0.01 ) {
  123.             Error( "Bad textureMatrix" );
  124.         }
  125.         s = fabs( DotProduct( b->xyz, f->textureMatrix[i] ) - b->st[i] );
  126.         if ( s > 0.01 ) {
  127.             Error( "Bad textureMatrix" );
  128.         }
  129.         s = fabs( DotProduct( c->xyz, f->textureMatrix[i] ) - c->st[i] );
  130.         if ( s > 0.01 ) {
  131.             Error( "Bad textureMatrix" );
  132.         }
  133. */
  134.     }
  135. }
  136.  
  137. /*
  138. =====================
  139. CM_GenerateFacetFor3Points
  140. =====================
  141. */
  142. qboolean CM_GenerateFacetFor3Points( cFacet_t *f, drawVert_t *a, drawVert_t *b, drawVert_t *c ) {
  143.     // if we can't generate a valid plane for the points, ignore the facet
  144.     if ( !PlaneFromPoints( f->surface, a->xyz, b->xyz, c->xyz ) ) {
  145.         f->numBoundaries = 0;
  146.         return qfalse;
  147.     }
  148.  
  149.     // make boundaries
  150.     f->numBoundaries = 3;
  151.  
  152.     CM_GenerateBoundaryForPoints( f->boundaries[0], f->surface, a->xyz, b->xyz );
  153.     CM_GenerateBoundaryForPoints( f->boundaries[1], f->surface, b->xyz, c->xyz );
  154.     CM_GenerateBoundaryForPoints( f->boundaries[2], f->surface, c->xyz, a->xyz );
  155.  
  156.     VectorCopy( a->xyz, f->points[0] );
  157.     VectorCopy( b->xyz, f->points[1] );
  158.     VectorCopy( c->xyz, f->points[2] );
  159.  
  160.     TextureMatrixFromPoints( f, a, b, c );
  161.  
  162.     return qtrue;
  163. }
  164.  
  165. /*
  166. =====================
  167. CM_GenerateFacetFor4Points
  168.  
  169. Attempts to use four points as a planar quad
  170. =====================
  171. */
  172. #define    PLANAR_EPSILON    0.1
  173. qboolean CM_GenerateFacetFor4Points( cFacet_t *f, drawVert_t *a, drawVert_t *b, drawVert_t *c, drawVert_t *d ) {
  174.     float    dist;
  175.     int        i;
  176.     vec4_t    plane;
  177.  
  178.     // if we can't generate a valid plane for the points, ignore the facet
  179.     if ( !PlaneFromPoints( f->surface, a->xyz, b->xyz, c->xyz ) ) {
  180.         f->numBoundaries = 0;
  181.         return qfalse;
  182.     }
  183.  
  184.     // if the fourth point is also on the plane, we can make a quad facet
  185.     dist = DotProduct( d->xyz, f->surface ) - f->surface[3];
  186.     if ( fabs( dist ) > PLANAR_EPSILON ) {
  187.         f->numBoundaries = 0;
  188.         return qfalse;
  189.     }
  190.  
  191.     // make boundaries
  192.     f->numBoundaries = 4;
  193.  
  194.     CM_GenerateBoundaryForPoints( f->boundaries[0], f->surface, a->xyz, b->xyz );
  195.     CM_GenerateBoundaryForPoints( f->boundaries[1], f->surface, b->xyz, c->xyz );
  196.     CM_GenerateBoundaryForPoints( f->boundaries[2], f->surface, c->xyz, d->xyz );
  197.     CM_GenerateBoundaryForPoints( f->boundaries[3], f->surface, d->xyz, a->xyz );
  198.  
  199.     VectorCopy( a->xyz, f->points[0] );
  200.     VectorCopy( b->xyz, f->points[1] );
  201.     VectorCopy( c->xyz, f->points[2] );
  202.     VectorCopy( d->xyz, f->points[3] );
  203.  
  204.     for (i = 1; i < 4; i++)
  205.     {
  206.         if ( !PlaneFromPoints( plane, f->points[i], f->points[(i+1) % 4], f->points[(i+2) % 4]) ) {
  207.             f->numBoundaries = 0;
  208.             return qfalse;
  209.         }
  210.  
  211.         if (DotProduct(f->surface, plane) < 0.9) {
  212.             f->numBoundaries = 0;
  213.             return qfalse;
  214.         }
  215.     }
  216.  
  217.     TextureMatrixFromPoints( f, a, b, c );
  218.  
  219.     return qtrue;
  220. }
  221.  
  222.  
  223.  
  224.  
  225. /*
  226. ===============
  227. SphereFromBounds
  228. ===============
  229. */
  230. void SphereFromBounds( vec3_t mins, vec3_t maxs, vec3_t origin, float *radius ) {
  231.     vec3_t        temp;
  232.  
  233.     VectorAdd( mins, maxs, origin );
  234.     VectorScale( origin, 0.5, origin );
  235.     VectorSubtract( maxs, origin, temp );
  236.     *radius = VectorLength( temp );
  237. }
  238.  
  239.  
  240. /*
  241. ====================
  242. FacetsForTriangleSurface
  243. ====================
  244. */
  245. void FacetsForTriangleSurface( dsurface_t *dsurf, shaderInfo_t *si, surfaceTest_t *test ) {
  246.     int            i;
  247.     drawVert_t    *v1, *v2, *v3, *v4;
  248.     int            count;
  249.     int            i1, i2, i3, i4, i5, i6;
  250.  
  251.     test->patch = qfalse;
  252.     test->numFacets = dsurf->numIndexes / 3;
  253.     test->facets = malloc( sizeof( test->facets[0] ) * test->numFacets );
  254.     test->shader = si;
  255.  
  256.     count = 0;
  257.     for ( i = 0 ; i < test->numFacets ; i++ ) {
  258.         i1 = drawIndexes[ dsurf->firstIndex + i*3 ];
  259.         i2 = drawIndexes[ dsurf->firstIndex + i*3 + 1 ];
  260.         i3 = drawIndexes[ dsurf->firstIndex + i*3 + 2 ];
  261.  
  262.         v1 = &drawVerts[ dsurf->firstVert + i1 ];
  263.         v2 = &drawVerts[ dsurf->firstVert + i2 ];
  264.         v3 = &drawVerts[ dsurf->firstVert + i3 ];
  265.  
  266.         // try and make a quad out of two triangles
  267.         if ( i != test->numFacets - 1 ) {
  268.             i4 = drawIndexes[ dsurf->firstIndex + i*3 + 3 ];
  269.             i5 = drawIndexes[ dsurf->firstIndex + i*3 + 4 ];
  270.             i6 = drawIndexes[ dsurf->firstIndex + i*3 + 5 ];
  271.             if ( i4 == i3 && i5 == i2 ) {
  272.                 v4 = &drawVerts[ dsurf->firstVert + i6 ];
  273.                 if ( CM_GenerateFacetFor4Points( &test->facets[count], v1, v2, v4, v3 ) ) {
  274.                     count++;
  275.                     i++;        // skip next tri
  276.                     continue;
  277.                 }
  278.             }
  279.         }
  280.  
  281.         if (CM_GenerateFacetFor3Points( &test->facets[count], v1, v2, v3 ))
  282.             count++;
  283.     }        
  284.  
  285.     // we may have turned some pairs into quads
  286.     test->numFacets = count;
  287. }
  288.  
  289. /*
  290. ====================
  291. FacetsForPatch
  292. ====================
  293. */
  294. void FacetsForPatch( dsurface_t *dsurf, shaderInfo_t *si, surfaceTest_t *test ) {
  295.     int            i, j;
  296.     drawVert_t    *v1, *v2, *v3, *v4;
  297.     int            count;
  298.     mesh_t        srcMesh, *subdivided, *mesh;
  299.  
  300.     srcMesh.width = dsurf->patchWidth;
  301.     srcMesh.height = dsurf->patchHeight;
  302.     srcMesh.verts = &drawVerts[ dsurf->firstVert ];
  303.  
  304.     //subdivided = SubdivideMesh( mesh, CURVE_FACET_ERROR, 9999 );
  305.     mesh = SubdivideMesh( srcMesh, 8, 999 );
  306.     PutMeshOnCurve( *mesh );
  307.     MakeMeshNormals( *mesh );
  308.  
  309.     subdivided = RemoveLinearMeshColumnsRows( mesh );
  310.     FreeMesh(mesh);
  311.  
  312.     test->patch = qtrue;
  313.     test->numFacets = ( subdivided->width - 1 ) * ( subdivided->height - 1 ) * 2;
  314.     test->facets = malloc( sizeof( test->facets[0] ) * test->numFacets );
  315.     test->shader = si;
  316.  
  317.     count = 0;
  318.     for ( i = 0 ; i < subdivided->width - 1 ; i++ ) {
  319.         for ( j = 0 ; j < subdivided->height - 1 ; j++ ) {
  320.  
  321.             v1 = subdivided->verts + j * subdivided->width + i;
  322.             v2 = v1 + 1;
  323.             v3 = v1 + subdivided->width + 1;
  324.             v4 = v1 + subdivided->width;
  325.  
  326.             if ( CM_GenerateFacetFor4Points( &test->facets[count], v1, v4, v3, v2 ) ) {
  327.                 count++;
  328.             } else {
  329.                 if (CM_GenerateFacetFor3Points( &test->facets[count], v1, v4, v3 ))
  330.                     count++;
  331.                 if (CM_GenerateFacetFor3Points( &test->facets[count], v1, v3, v2 ))
  332.                     count++;
  333.             }
  334.         }
  335.     }
  336.     test->numFacets = count;
  337.     FreeMesh(subdivided);
  338. }
  339.  
  340.  
  341. /*
  342. =====================
  343. InitSurfacesForTesting
  344.  
  345. Builds structures to speed the ray tracing against surfaces
  346. =====================
  347. */
  348. void InitSurfacesForTesting( void ) {
  349.  
  350.     int                i, j;
  351.     dsurface_t        *dsurf;
  352.     surfaceTest_t    *test;
  353.     drawVert_t        *dvert;
  354.     shaderInfo_t    *si;
  355.  
  356.     for ( i = 0 ; i < numDrawSurfaces ; i++ ) {
  357.         dsurf = &drawSurfaces[ i ];
  358.         if ( !dsurf->numIndexes && !dsurf->patchWidth ) {
  359.             continue;
  360.         }
  361.  
  362.         // don't make surfaces for transparent objects
  363.         // because we want light to pass through them
  364.         si = ShaderInfoForShader( dshaders[ dsurf->shaderNum].shader );
  365.         if ( (si->contents & CONTENTS_TRANSLUCENT) && !(si->surfaceFlags & SURF_ALPHASHADOW) ) {
  366.             continue;
  367.         }
  368.  
  369.         test = malloc( sizeof( *test ) );
  370.         surfaceTest[i] = test;
  371.         ClearBounds( test->mins, test->maxs );
  372.  
  373.         dvert = &drawVerts[ dsurf->firstVert ];
  374.         for ( j = 0 ; j < dsurf->numVerts ; j++, dvert++ ) {
  375.             AddPointToBounds( dvert->xyz, test->mins, test->maxs );
  376.         }
  377.  
  378.         SphereFromBounds( test->mins, test->maxs, test->origin, &test->radius );
  379.  
  380.         if ( dsurf->surfaceType == MST_TRIANGLE_SOUP || dsurf->surfaceType == MST_PLANAR ) {
  381.             FacetsForTriangleSurface( dsurf, si, test );
  382.         } else if ( dsurf->surfaceType == MST_PATCH ) {
  383.             FacetsForPatch( dsurf, si, test );
  384.         }
  385.     }
  386. }
  387.  
  388.  
  389. /*
  390. =====================
  391. GenerateBoundaryForPoints
  392. =====================
  393. */
  394. void GenerateBoundaryForPoints( float boundary[4], float plane[4], vec3_t a, vec3_t b ) {
  395.     vec3_t    d1;
  396.  
  397.     // amke a perpendicular vector to the edge and the surface
  398.     VectorSubtract( b, a, d1 );
  399.     CrossProduct( plane, d1, boundary );
  400.     VectorNormalize( boundary, boundary );
  401.     boundary[3] = DotProduct( a, boundary );
  402. }
  403.  
  404.  
  405. /*
  406. =================
  407. SetFacetFilter
  408.  
  409. Given a point on a facet, determine the color filter
  410. for light passing through
  411. =================
  412. */
  413. void SetFacetFilter( traceWork_t *tr, shaderInfo_t *shader, cFacet_t *facet, vec3_t point ) {
  414.     float    s, t;
  415.     int        is, it;
  416.     byte    *image;
  417.     int        b;
  418.  
  419.     // most surfaces are completely opaque
  420.     if ( !(shader->surfaceFlags & SURF_ALPHASHADOW) ) {
  421.         VectorClear( tr->trace->filter );
  422.         return;
  423.     }
  424.  
  425.     s = DotProduct( point, facet->textureMatrix[0] ) + facet->textureMatrix[0][3];
  426.     t = DotProduct( point, facet->textureMatrix[1] ) + facet->textureMatrix[1][3];
  427.  
  428.     if ( !shader->pixels ) {
  429.         // assume completely solid
  430.         VectorClear( point );
  431.         return;
  432.     }
  433.  
  434.     s = s - floor( s );
  435.     t = t - floor( t );
  436.  
  437.     is = s * shader->width;
  438.     it = t * shader->height;
  439.  
  440.     image = shader->pixels + 4 * ( it * shader->width + is );
  441.  
  442.     // alpha filter
  443.     b = image[3];
  444.  
  445.     // alpha test makes this a binary option
  446.     b = b < 128 ? 0 : 255;
  447.  
  448.     tr->trace->filter[0] = tr->trace->filter[0] * (255-b) / 255;
  449.     tr->trace->filter[1] = tr->trace->filter[1] * (255-b) / 255;
  450.     tr->trace->filter[2] = tr->trace->filter[2] * (255-b) / 255;
  451. }
  452.  
  453.  
  454. /*
  455. ====================
  456. TraceAgainstFacet
  457.  
  458. Shader is needed for translucent surfaces
  459. ====================
  460. */
  461. void TraceAgainstFacet( traceWork_t *tr, shaderInfo_t *shader, cFacet_t *facet ) {
  462.     int            j;
  463.     float        d1, d2, d, f;
  464.     vec3_t        point;
  465.     float        dist;
  466.  
  467.     // ignore degenerate facets
  468.     if ( facet->numBoundaries < 3 ) {
  469.         return;
  470.     }
  471.  
  472.     dist = facet->surface[3];
  473.  
  474.     // compare the trace endpoints against the facet plane
  475.     d1 = DotProduct( tr->start, facet->surface ) - dist;
  476.     if ( d1 > -1 && d1 < 1 ) {
  477.         return;        // don't self intersect
  478.     }
  479.     d2 = DotProduct( tr->end, facet->surface ) - dist;
  480.     if ( d2 > -1 && d2 < 1 ) {
  481.         return;        // don't self intersect
  482.     }
  483.  
  484.     // calculate the intersection fraction
  485.     f = ( d1 - ON_EPSILON ) / ( d1 - d2 );
  486.     if ( f <= 0 ) {
  487.         return;
  488.     }
  489.     if ( f >= tr->trace->hitFraction ) {
  490.         return;            // we have hit something earlier
  491.     }
  492.  
  493.     // calculate the intersection point
  494.     for ( j = 0 ; j < 3 ; j++ ) {
  495.         point[j] = tr->start[j] + f * ( tr->end[j] - tr->start[j] );
  496.     }
  497.  
  498.     // check the point against the facet boundaries
  499.     for ( j = 0 ; j < facet->numBoundaries ; j++ ) {
  500.         // adjust the plane distance apropriately for mins/maxs
  501.         dist = facet->boundaries[j][3];
  502.  
  503.         d = DotProduct( point, facet->boundaries[j] );
  504.         if ( d > dist + ON_EPSILON ) {
  505.             break;        // outside the bounds
  506.         }
  507.     }
  508.  
  509.     if ( j != facet->numBoundaries ) {
  510.         return;            // we are outside the bounds of the facet
  511.     }
  512.  
  513.     // we hit this facet
  514.  
  515.     // if this is a transparent surface, calculate filter value
  516.     if ( shader->surfaceFlags & SURF_ALPHASHADOW ) {
  517.         SetFacetFilter( tr, shader, facet, point );
  518.     } else {
  519.         // completely opaque
  520.         VectorClear( tr->trace->filter );
  521.         tr->trace->hitFraction = f;
  522.     }
  523.  
  524. //    VectorCopy( facet->surface, tr->trace->plane.normal );
  525. //    tr->trace->plane.dist = facet->surface[3];
  526. }
  527.  
  528.  
  529. /*
  530. ===============================================================
  531.  
  532.   LINE TRACING
  533.  
  534. ===============================================================
  535. */
  536.  
  537.  
  538. #define    TRACE_ON_EPSILON    0.1
  539.  
  540. typedef struct tnode_s
  541. {
  542.     int        type;
  543.     vec3_t    normal;
  544.     float    dist;
  545.     int        children[2];
  546.     int        planeNum;
  547. } tnode_t;
  548.  
  549. #define    MAX_TNODES    (MAX_MAP_NODES*4)
  550. tnode_t        *tnodes, *tnode_p;
  551.  
  552. /*
  553. ==============
  554. MakeTnode
  555.  
  556. Converts the disk node structure into the efficient tracing structure
  557. ==============
  558. */
  559. void MakeTnode (int nodenum)
  560. {
  561.     tnode_t            *t;
  562.     dplane_t        *plane;
  563.     int                i;
  564.     dnode_t         *node;
  565.     int                leafNum;
  566.  
  567.     t = tnode_p++;
  568.  
  569.     node = dnodes + nodenum;
  570.     plane = dplanes + node->planeNum;
  571.  
  572.     t->planeNum = node->planeNum;
  573.     t->type = PlaneTypeForNormal( plane->normal );
  574.     VectorCopy (plane->normal, t->normal);
  575.     t->dist = plane->dist;
  576.     
  577.     for (i=0 ; i<2 ; i++)
  578.     {
  579.         if (node->children[i] < 0) {
  580.             leafNum = -node->children[i] - 1;
  581.             if ( dleafs[leafNum].cluster == -1  ) {
  582.                 // solid
  583.                 t->children[i] = leafNum | ( 1 << 31 ) | ( 1 << 30 );
  584.             } else {
  585.                 t->children[i] = leafNum | ( 1 << 31 );
  586.             }
  587.         } else {
  588.             t->children[i] = tnode_p - tnodes;
  589.             MakeTnode (node->children[i]);
  590.         }
  591.     }
  592.             
  593. }
  594.  
  595. /*
  596. =============
  597. InitTrace
  598.  
  599. Loads the node structure out of a .bsp file to be used for light occlusion
  600. =============
  601. */
  602. void InitTrace( void ) {
  603.     // 32 byte align the structs
  604.     tnodes = malloc( (MAX_TNODES+1) * sizeof(tnode_t));
  605.     tnodes = (tnode_t *)(((int)tnodes + 31)&~31);
  606.     tnode_p = tnodes;
  607.  
  608.     MakeTnode (0);
  609.  
  610.     InitSurfacesForTesting();
  611. }
  612.  
  613.  
  614. /*
  615. ===================
  616. PointInSolid
  617. ===================
  618. */
  619. qboolean PointInSolid_r( vec3_t start, int node ) {
  620.     tnode_t    *tnode;
  621.     float    front;
  622.  
  623.     while ( !(node & (1<<31) ) ) {
  624.         tnode = &tnodes[node];
  625.         switch (tnode->type) {
  626.         case PLANE_X:
  627.             front = start[0] - tnode->dist;
  628.             break;
  629.         case PLANE_Y:
  630.             front = start[1] - tnode->dist;
  631.             break;
  632.         case PLANE_Z:
  633.             front = start[2] - tnode->dist;
  634.             break;
  635.         default:
  636.             front = (start[0]*tnode->normal[0] + start[1]*tnode->normal[1] + start[2]*tnode->normal[2]) - tnode->dist;
  637.             break;
  638.         }
  639.  
  640.         if ( front == 0 ) {
  641.             // exactly on node, must check both sides
  642.             return (qboolean) ( PointInSolid_r( start, tnode->children[0] ) 
  643.                 | PointInSolid_r( start, tnode->children[1] ) );
  644.         }
  645.  
  646.         if ( front > 0 ) {
  647.             node = tnode->children[0];
  648.         } else {
  649.             node = tnode->children[1];
  650.         }
  651.     }
  652.  
  653.     if ( node & ( 1 << 30 ) ) {
  654.         return qtrue;
  655.     }
  656.     return qfalse;
  657. }
  658.  
  659. /*
  660. =============
  661. PointInSolid
  662.  
  663. =============
  664. */
  665. qboolean PointInSolid( vec3_t start ) {
  666.     return PointInSolid_r( start, 0 );
  667. }
  668.  
  669.  
  670. /*
  671. =============
  672. TraceLine_r
  673.  
  674. Returns qtrue if something is hit and tracing can stop
  675. =============
  676. */
  677. int TraceLine_r( int node, const vec3_t start, const vec3_t stop, traceWork_t *tw ) {
  678.     tnode_t    *tnode;
  679.     float    front, back;
  680.     vec3_t    mid;
  681.     float    frac;
  682.     int        side;
  683.     int        r;
  684.  
  685.     if (node & (1<<31)) {
  686.         if (node & ( 1 << 30 ) ) {
  687.             VectorCopy (start, tw->trace->hit);
  688.             tw->trace->passSolid = qtrue;
  689.             return qtrue;
  690.         } else {
  691.             // save the node off for more exact testing
  692.             if ( tw->numOpenLeafs == MAX_MAP_LEAFS ) {
  693.                 return qfalse;
  694.             }
  695.             tw->openLeafNumbers[ tw->numOpenLeafs ] = node & ~(3 << 30);
  696.             tw->numOpenLeafs++;
  697.             return qfalse;
  698.         }
  699.     }
  700.  
  701.     tnode = &tnodes[node];
  702.     switch (tnode->type) {
  703.     case PLANE_X:
  704.         front = start[0] - tnode->dist;
  705.         back = stop[0] - tnode->dist;
  706.         break;
  707.     case PLANE_Y:
  708.         front = start[1] - tnode->dist;
  709.         back = stop[1] - tnode->dist;
  710.         break;
  711.     case PLANE_Z:
  712.         front = start[2] - tnode->dist;
  713.         back = stop[2] - tnode->dist;
  714.         break;
  715.     default:
  716.         front = (start[0]*tnode->normal[0] + start[1]*tnode->normal[1] + start[2]*tnode->normal[2]) - tnode->dist;
  717.         back = (stop[0]*tnode->normal[0] + stop[1]*tnode->normal[1] + stop[2]*tnode->normal[2]) - tnode->dist;
  718.         break;
  719.     }
  720.  
  721.     if (front >= -TRACE_ON_EPSILON && back >= -TRACE_ON_EPSILON) {
  722.         return TraceLine_r (tnode->children[0], start, stop, tw);
  723.     }
  724.     
  725.     if (front < TRACE_ON_EPSILON && back < TRACE_ON_EPSILON) {
  726.         return TraceLine_r (tnode->children[1], start, stop, tw);
  727.     }
  728.  
  729.     side = front < 0;
  730.     
  731.     frac = front / (front-back);
  732.  
  733.     mid[0] = start[0] + (stop[0] - start[0])*frac;
  734.     mid[1] = start[1] + (stop[1] - start[1])*frac;
  735.     mid[2] = start[2] + (stop[2] - start[2])*frac;
  736.  
  737.     r = TraceLine_r (tnode->children[side], start, mid, tw);
  738.  
  739.     if (r) {
  740.         return r;
  741.     }
  742.  
  743. //    trace->planeNum = tnode->planeNum;
  744.     return TraceLine_r (tnode->children[!side], mid, stop, tw);
  745. }
  746.  
  747. //==========================================================================================
  748.  
  749.  
  750. /*
  751. ================
  752. SphereCull
  753. ================
  754. */
  755. qboolean    SphereCull( vec3_t start, vec3_t stop, vec3_t origin, float radius ) {
  756.     vec3_t        v;
  757.     float        d;
  758.     vec3_t        dir;
  759.     float        len;
  760.     vec3_t        on;
  761.  
  762.     VectorSubtract( stop, start, dir );
  763.     len = VectorNormalize( dir, dir );
  764.  
  765.     VectorSubtract( origin, start, v );
  766.     d = DotProduct( v, dir );
  767.     if ( d > len + radius ) {
  768.         return qtrue;        // too far ahead
  769.     }
  770.     if ( d < -radius ) {
  771.         return qtrue;        // too far behind
  772.     }
  773.     VectorMA( start, d, dir, on );
  774.     
  775.     VectorSubtract( on, origin, v );
  776.  
  777.     len = VectorLength( v );
  778.  
  779.     if ( len > radius ) {
  780.         return qtrue;        // too far to the side
  781.     }
  782.  
  783.     return qfalse;        // must be traced against
  784. }
  785.  
  786. /*
  787. ================
  788. TraceAgainstSurface
  789. ================
  790. */
  791. void    TraceAgainstSurface( traceWork_t *tw, surfaceTest_t *surf ) {
  792.     int        i;
  793.  
  794.     // if surfaces are trans
  795.     if ( SphereCull( tw->start, tw->end, surf->origin, surf->radius ) ) {
  796.         if ( numthreads == 1 ) {
  797.             c_cullTrace++;
  798.         }
  799.         return;
  800.     }
  801.  
  802.     if ( numthreads == 1 ) {
  803.         c_testTrace++;
  804.         c_testFacets += surf->numFacets;
  805.     }
  806.  
  807.     /*
  808.     // MrE: backface culling
  809.     if (!surf->patch && surf->numFacets) {
  810.         // if the surface does not cast an alpha shadow
  811.         if ( !(surf->shader->surfaceFlags & SURF_ALPHASHADOW) ) {
  812.             vec3_t vec;
  813.             VectorSubtract(tw->end, tw->start, vec);
  814.             if (DotProduct(vec, surf->facets->surface) > 0)
  815.                 return;
  816.         }
  817.     }
  818.     */
  819.  
  820.     // test against each facet
  821.     for ( i = 0 ; i < surf->numFacets ; i++ ) {
  822.         TraceAgainstFacet( tw, surf->shader, surf->facets + i );
  823.     }
  824. }
  825.  
  826. /*
  827. =============
  828. TraceLine
  829.  
  830. Follow the trace just through the solid leafs first, and only
  831. if it passes that, trace against the objects inside the empty leafs
  832. Returns qtrue if the trace hit any
  833.  
  834. traceWork_t is only a parameter to crutch up poor large local allocations on
  835. winNT and macOS.  It should be allocated in the worker function, but never
  836. looked at.
  837.  
  838. leave testAll false if all you care about is if it hit anything at all.
  839. if you need to know the exact first point of impact (for a sun trace), set
  840. testAll to true
  841. =============
  842. */
  843. extern qboolean    patchshadows;
  844.  
  845. void TraceLine( const vec3_t start, const vec3_t stop, trace_t *trace, qboolean testAll, traceWork_t *tw ) {
  846.     int                r;
  847.     int                i, j;
  848.     dleaf_t            *leaf;
  849.     float            oldHitFrac;
  850.     surfaceTest_t    *test;
  851.     int                surfaceNum;
  852.     byte            surfaceTested[MAX_MAP_DRAW_SURFS/8];
  853.     ;
  854.  
  855.     if ( numthreads == 1 ) {
  856.         c_totalTrace++;
  857.     }
  858.  
  859.     // assume all light gets through, unless the ray crosses
  860.     // a translucent surface
  861.     trace->filter[0] = 1.0;
  862.     trace->filter[1] = 1.0;
  863.     trace->filter[2] = 1.0;
  864.  
  865.     VectorCopy( start, tw->start );
  866.     VectorCopy( stop, tw->end );
  867.     tw->trace = trace;
  868.  
  869.     tw->numOpenLeafs = 0;
  870.  
  871.     trace->passSolid = qfalse;
  872.     trace->hitFraction = 1.0;
  873.  
  874.     r = TraceLine_r( 0, start, stop, tw );
  875.  
  876.     // if we hit a solid leaf, stop without testing the leaf
  877.     // surfaces.  Note that the plane and endpoint might not
  878.     // be the first solid intersection along the ray.
  879.     if ( r && !testAll ) {
  880.         return;
  881.     }
  882.  
  883.     if ( noSurfaces ) {
  884.         return;
  885.     }
  886.  
  887.     memset( surfaceTested, 0, (numDrawSurfaces+7)/8 );
  888.     oldHitFrac = trace->hitFraction;
  889.  
  890.     for ( i = 0 ; i < tw->numOpenLeafs ; i++ ) {
  891.         leaf = &dleafs[ tw->openLeafNumbers[ i ] ];
  892.         for ( j = 0 ; j < leaf->numLeafSurfaces ; j++ ) {
  893.             surfaceNum = dleafsurfaces[ leaf->firstLeafSurface + j ];
  894.  
  895.             // make sure we don't test the same ray against a surface more than once
  896.             if ( surfaceTested[ surfaceNum>>3 ] & ( 1 << ( surfaceNum & 7) ) ) {
  897.                 continue;
  898.             }
  899.             surfaceTested[ surfaceNum>>3 ] |= ( 1 << ( surfaceNum & 7 ) );
  900.  
  901.             test = surfaceTest[ surfaceNum ];
  902.             if ( !test ) {
  903.                 continue;
  904.             }
  905.             //
  906.             if ( !tw->patchshadows && test->patch ) {
  907.                 continue;
  908.             }
  909.             TraceAgainstSurface( tw, test );
  910.         }
  911.  
  912.         // if the trace is now solid, we can't possibly hit anything closer
  913.         if ( trace->hitFraction < oldHitFrac ) {
  914.             trace->passSolid = qtrue;
  915.             break;
  916.         }
  917.     }
  918.     
  919.     for ( i = 0 ; i < 3 ; i++ ) {
  920.         trace->hit[i] = start[i] + ( stop[i] - start[i] ) * trace->hitFraction;
  921.     }
  922. }
  923.  
  924.